A data array, or data structure, is a means of storing data in a computer system so that the data can be organized, accessed, and used. A fundamental unit of a typical data array is a node. Conventional nodes may store any amount of data, including another data array. The size of a node is typically determined by the designer of the data array.
Data arrays can have a variety of structures. One such structure is a binary tree. In a binary tree, nodes that store data are linked so that each node has only one parent and at most two children. In binary trees, nodes are typically arranged in horizontal rows called levels, such that, for example, a parent node is one level above its two children nodes. Binary search trees may be self-balancing so that the number of levels, or the tree's height, is kept as small as possible. Minimizing the height of the tree minimizes the number of nodes that are searched to find requested data. One such self-balancing binary tree is an AVL tree (so named for its inventors, G. M. Adelson-Velsky and E. M. Landis). Typically, AVL trees are stored in contiguous memory.
Data within a binary tree may be segmented into pages. A page is typically a block of main memory that contains the physical and virtual memory address of data or a data node. Pages are generally contiguous and are of uniform size.
As new data is added to a binary tree, the tree becomes larger and more complex, resulting in increased time and operating costs for storing and looking up data within a data tree. Even with its self-balancing feature, a binary tree can grow to a large size, making it difficult to store data, and search for data, within it.